//45.跳跃游戏II https://leetcode-cn.com/problems/jump-game-ii/submissions/
class Solution {
public:
    int jump(vector<int>& nums) {
        int nextmax = 0;
        int curmax = 0;
        int count = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            nextmax = max(nextmax, i + nums[i]);
            if(curmax == i)
            {
                //假设当前的最大覆盖范围也就是i的地方还没到终点
                if(curmax != nums.size() - 1)
                {
                    //就把下一个最大覆盖范围给当前最大覆盖范围
                    curmax = nextmax;
                    count++;
                    //如果超过了最大范围就可以直接返回了
                    if(curmax >= nums.size() - 1) break;
                }
                else
                    break;
            }
        }
        return count;
    }
};

//55.跳跃游戏I https://leetcode-cn.com/problems/jump-game/


class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
		//假设只有一个元素的时候就可以直接返回了
        if(nums.size() == 1) 
            return true;
		//i最大跳到cover上
        for(int i = 0 ; i <= cover ; i++)
        {
			//每次找最大可以跳跃到的范围
            cover = max(cover , i + nums[i]);
            if(cover >= nums.size() - 1) return true;
        }
        return false;
    }
};